#include <iostream>  
#include <cstring>

using namespace std;  
  
/** 
*KMP-Table 
*input: pattern  
*output : next[] 
*/  
void kmp_table(const char * P, int * next)  
{  
    next[0] = -1;  
    next[1] = 0;  
    unsigned int j = 2;  
    int cnd = 0;  
  
    while(j < strlen(P))  
    {  
        if( P[j-1] == P[cnd])  
        {  
            next[j] = cnd + 1;  
            ++j;  
            ++cnd;  
        }  
        else if( cnd > 0)  
            cnd = next[cnd];  
        else   
        {  
            next[j] = 0;  
            ++j;  
        }  
    }  
}  
  
/** 
*KMP_Search 
*input: char * Target ;  char * Pattern: 
*output ; the position of the Pattern in Traget; 
**/  
int kmp_search(const char * T, const char * P)  
{  
    int n = strlen(T);  
    int m = strlen(P);  
    int * next = new int[m];  
    int j = 0;  
  
    kmp_table(P,next);  
  
    for( int k = 0; k < m; k++)  
    {  
        cout<<next[k]<< "" ;  
    }  
    cout<<endl;  
  
    for( int i = 0; i < n; i++)  
    {  
        for(;;)  
        {  
            if( T[i] == P[j])  
            {  
                j++;  
                if(j == m)  
                    return i-m + 1  ;  
                break;  
            }  
            else if(j == 0) break;  
            else  
            {  
                j = next[j];  
            }  
        }  
    }  
    return -1;  
}  
  
int main()  
{  
    char * S = "acabaabaabcacaabc";  
    char * W = "abaabcac";  
  
    int p = kmp_search(S,W);  
  
    cout<<"p = "<< p <<endl;  
}  
